1. Field of the Invention
The present invention relates to a difference degree evaluation device which is used, for example, for a search of corresponding points between images, a difference degree evaluation method, and a program product.
2. Description of the Related Art
A search for corresponding points between a plurality of images is important in order to execute motion compensation, alignment and optical flow estimation. General methods for the search for corresponding points are area-based matching methods such as template matching and block matching.
It is now assumed that one of two images, which are objects of matching, is called “reference image” and the other is called “object image”. In the template matching, a block of a predetermined size, which is set at an arbitrary position of the reference image, is used as a template, and a search is executed to find which position in the object image corresponds to each pixel in the template.
At this time, as a measure for evaluating the degree of matching, SSD (Sum of Squared Difference) or SAD (Sum of Absolute Difference) is used. The SSD and SAD indicate difference degrees. It is considered that matching is better as the evaluation value is lower. Jpn. Pat. Appln. KOKAI Publication No. 10-289315, for instance, discloses a matching method using SSD.
The formal definitions of SSD and SAD are as follows:
                              S          ⁢                                          ⁢          S          ⁢                                          ⁢                      D            ⁡                          (              d              )                                      =                              ∑                          p              ∈              T                                ⁢                                    (                                                R                  p                                -                                  O                                      p                    +                    d                                                              )                        2                                              (        1        )                                          S          ⁢                                          ⁢          A          ⁢                                          ⁢                      D            ⁡                          (              d              )                                      =                              ∑                          p              ∈              T                                ⁢                                                                R                p                            -                              O                                  p                  +                  d                                                                                                    (        2        )            
In the equations (1) and (2), the pixel value at the coordinates p of the reference image is expressed as Rp, and similarly the pixel value at the coordinates p of the object image is expressed as Op. Symbol p represents a position vector. If p=(px, py), an x component is px and a y component is py.
In addition, the set of coordinates of pixels, which constitute the template, is T. For example, in the case where a rectangular block of 16×16 pixels, whose upper left corner coordinates are (100, 200), is used as a template, the set T comprises the following 256 pixels.
T={(100, 200), (101, 200), . . . , (115, 200), (100, 201), (101, 201), . . . , (115, 201), . . . , (100, 215), (101, 215), . . . , (115, 215)}
In addition, parallel movement of coordinates in the object image from the reference image is expressed by a vector d. The SSD of equation (1) and the SAD of equation (2) are functions of d.
The SAD is advantageous in that the arithmetic operation is simple and thus the SAD can easily be implemented. However, a difference in brightness occurs between images in the case where successive photography is executed, for example, under a fluorescent lamp, or in the case where images, which are photographed by using an optical system with high dimming characteristics, are mosaic-synthesized (e.g. synthesis of a panorama image).
In the case where images having such a difference in brightness are set as objects of matching, the robustness of matching will considerably decrease in the SAD. The reason for this is that if the brightness levels of two images are sharply different, the absolute value operation becomes meaningless, and the SAD becomes equivalent to a mere sum of differences. In such a case, mean values of signals (DC components) are merely compared, and matching of local irregularities can hardly be executed.
In order to make the explanation simple, one-dimensional signals, as shown in FIG. 15, are now exemplified.
Symbol ai denotes a reference signal, and bi denotes an object signal. Crest portions of the respective signals indicate corresponding parts. In this case, from the equation (2), SAD is expressed bySAD=Σ|ai−bi|  (3)
If the levels of ai and bi are greatly different, the equation (3) becomes equivalent to Σai−Σbi, and matching cannot be executed at any point, as shown in a comparison result in FIG. 17.
In the example of FIG. 17, four sample points are used as a template. The signal bi is a signal to which a negative DC offset is applied, relative to ai, and is displaced from ai by one sample. If there is a level difference, the value of SAD becomes the same at any point (“4” in this example).
On the other hand, from the equation (1), the SSD is expressed bySSD=Σ(ai−bi)2  (4)
The SSD is a measure which emphasizes the local peak property of a difference. Thus, even in the same situation, relatively robust matching can be executed. On the other hand, since the SSD is based on a squaring arithmetic operation, hardware for multiplication is needed and the processing speed is low. Moreover, in the multiplication result of the SSD, about double number of digits are generated, compared to absolute values used in the SAD. As a result, the circuit scale increases.
As has been described above, the SAD is easily to implement, but is not robust to a level variation between signals. On the other hand, the SSD is relatively robust to a level variation between signals, but the circuit scale increases.